package com.lw.leetcode.bingChaJi.b;

import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * 1584. 连接所有点的最小费用
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/3 15:09
 */
public class MinCostConnectPoints {

    public static void main(String[] args) {
        MinCostConnectPoints test = new MinCostConnectPoints();

        // 20
//        int[][] points = {{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}};

        // 4
//        int[][] points = {{0, 0}, {1, 1}, {1, 0}, {-1, 1}};

        // 4000000
//        int[][] points = {{-1000000, -1000000}, {1000000, 1000000}};

        // 0
        int[][] points = {{0, 0}};

        int i = test.minCostConnectPoints(points);
        System.out.println(i);
    }

    public int minCostConnectPoints(int[][] points) {
        int length = points.length;
        PriorityQueue<Long> queue = new PriorityQueue<>();
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                long v = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                queue.add((v << 32) + (j << 12) + (i));
            }
        }
        int sum = 0;
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            arr[i] = i;
        }
        while (!queue.isEmpty()) {
            long poll = queue.poll();
            int i = find(arr, (int) ((poll >> 12) & 0XFFF));
            int j = find(arr, (int) (poll & 0XFFF));
            if (i == j) {
                continue;
            }
            sum += (poll >> 32);
            arr[j] = i;
        }
        return sum;
    }

    private int find(int[] arr, int t) {
        if (arr[t] == t) {
            return t;
        }
        int v = find(arr, arr[t]);
        arr[t] = v;
        return v;
    }

}
